import java.util.ArrayList;
import java.util.List;

class Solution315 {
    int[] arr1 ;   // 用来记录元素发生改变
    int[] arr2 ;  // 用记录 元素对应的原始下标发生的改变
     int[] sum ;
     int[] indexs ;
    public List<Integer> countSmaller(int[] nums) {
          List<Integer> list = new ArrayList<>() ;
          int len = nums.length ;
          sum = new int[len] ; 
          arr1 = new int[len] ; 
          arr2 = new int[len] ; 
          indexs = new int[len] ; 
          for(int i=0 ; i < len ; i ++) indexs[i] = i ;
          merge(nums , 0 , len-1) ; 
          for(int i: sum) {
            list.add(i) ; 
          }
          return list ;
    }
    private void merge(int[] nums , int left , int right ){
        if(left >= right) return ; 
        int mid = left + (right-left)/2 ;
        merge(nums,left , mid) ; 
        merge(nums,mid+1 , right) ; 
        int l = left , r = mid+1 , i = 0 ;
        while(l <= mid  && r <= right){
          if(nums[l] > nums[r]){
            sum[indexs[l]] += right-r+1 ;
            arr1[i] = nums[l] ;
            arr2[i++] = indexs[l++] ; 
          }else{
            arr1[i] = nums[r] ; 
            arr2[i++] = indexs[r++] ; 
          }
        }
        while(l <= mid){
            arr1[i] = nums[l] ; 
            arr2[i++] = indexs[l++] ; 
        }
        while(r <= right){
            arr1[i] = nums[r] ; 
            arr2[i++] = indexs[r++] ; 
        }
        for(int j=left ; j <= right ; j++){
            nums[j] = arr1[j-left] ; 
            indexs[j] = arr2[j-left] ; 
        }
    }

}